{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Twin Sum of a Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pairSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #链表最大孪生和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个大小为&nbsp;<code>n</code>&nbsp;且 <code>n</code>&nbsp;为&nbsp;<strong>偶数</strong> 的链表中，对于&nbsp;<code>0 &lt;= i &lt;= (n / 2) - 1</code>&nbsp;的 <code>i</code>&nbsp;，第&nbsp;<code>i</code>&nbsp;个节点（下标从 <strong>0</strong>&nbsp;开始）的孪生节点为第&nbsp;<code>(n-1-i)</code>&nbsp;个节点 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>n = 4</code>&nbsp;那么节点&nbsp;<code>0</code>&nbsp;是节点 <code>3</code>&nbsp;的孪生节点，节点 <code>1</code>&nbsp;是节点 <code>2</code>&nbsp;的孪生节点。这是长度为 <code><span style=\"\">n = 4</span></code>&nbsp;的链表中所有的孪生节点。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>孪生和</strong>&nbsp;定义为一个节点和它孪生节点两者值之和。</p>\n",
    "\n",
    "<p>给你一个长度为偶数的链表的头节点&nbsp;<code>head</code>&nbsp;，请你返回链表的 <strong>最大孪生和</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/03/eg1drawio.png\" style=\"width: 250px; height: 70px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>head = [5,4,2,1]\n",
    "<b>输出：</b>6\n",
    "<strong>解释：</strong>\n",
    "节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。\n",
    "链表中没有其他孪生节点。\n",
    "所以，链表的最大孪生和是 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/03/eg2drawio.png\" style=\"width: 250px; height: 70px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>head = [4,2,2,3]\n",
    "<b>输出：</b>7\n",
    "<strong>解释：</strong>\n",
    "链表中的孪生节点为：\n",
    "- 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。\n",
    "- 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。\n",
    "所以，最大孪生和为 max(7, 4) = 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/03/eg3drawio.png\" style=\"width: 200px; height: 88px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>head = [1,100000]\n",
    "<b>输出：</b>100001\n",
    "<strong>解释：</strong>\n",
    "链表中只有一对孪生节点，孪生和为 1 + 100000 = 100001 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表的节点数目是&nbsp;<code>[2, 10<sup>5</sup>]</code>&nbsp;中的&nbsp;<strong>偶数</strong>&nbsp;。</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-twin-sum-of-a-linked-list](https://leetcode.cn/problems/maximum-twin-sum-of-a-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-twin-sum-of-a-linked-list](https://leetcode.cn/problems/maximum-twin-sum-of-a-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,2,1]', '[4,2,2,3]', '[1,100000]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        slow = head\n",
    "        fast = head.next\n",
    "        first_half = list()\n",
    "        first_half.append(slow.val)\n",
    "        while fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            first_half.append(slow.val)\n",
    "        \n",
    "        ans = 0\n",
    "        i = len(first_half)-1\n",
    "        slow = slow.next\n",
    "        while slow:\n",
    "            ans = max(ans, slow.val+first_half[i])\n",
    "            slow = slow.next\n",
    "            i-=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        slow_prev, slow, fast = None, head, head\n",
    "\n",
    "        while fast is not None and fast.next is not None:\n",
    "            fast = fast.next.next\n",
    "            slow.next, slow_prev, slow = slow_prev, slow, slow.next\n",
    "\n",
    "        max_val = 0\n",
    "        while slow_prev is not None and slow is not None:\n",
    "            val = slow.val + slow_prev.val\n",
    "            if val > max_val:\n",
    "                max_val = val\n",
    "\n",
    "            slow_prev = slow_prev.next\n",
    "            slow = slow.next\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head):\n",
    "        slow, fast, pre = head, head, None\n",
    "        while fast and fast.next:\n",
    "            fast=fast.next.next\n",
    "            tmp=slow.next\n",
    "            slow.next=pre\n",
    "            pre=slow\n",
    "            slow=tmp\n",
    "        fast=tmp\n",
    "        slow=pre\n",
    "        maxsum=0\n",
    "        while fast:\n",
    "            maxsum=max(maxsum,slow.val+fast.val)\n",
    "            slow=slow.next\n",
    "            fast=fast.next\n",
    "        return maxsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        last = None\n",
    "        reverse_head = None\n",
    "        slow_node = head\n",
    "        fast_node = head.next\n",
    "        while fast_node.next:\n",
    "            reverse_head = slow_node\n",
    "            slow_node = slow_node.next\n",
    "            fast_node = fast_node.next.next\n",
    "            reverse_head.next = last\n",
    "            last = reverse_head\n",
    "        ans = 0\n",
    "        reverse_head = slow_node\n",
    "        slow_node = slow_node.next\n",
    "        reverse_head.next = last\n",
    "        while slow_node:\n",
    "            ans = max(ans, slow_node.val + reverse_head.val)\n",
    "            slow_node = slow_node.next\n",
    "            reverse_head = reverse_head.next\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        slow,fast = head, head\n",
    "        p = None\n",
    "        n = head.next\n",
    "        while fast.next:\n",
    "            fast = fast.next\n",
    "            if fast.next:\n",
    "                fast = fast.next\n",
    "            slow.next = p\n",
    "            p = slow\n",
    "            slow = n\n",
    "            n = slow.next\n",
    "        ans = p.val+slow.val\n",
    "        p = p.next\n",
    "        slow = slow.next\n",
    "        while p:\n",
    "            ans = max(ans, p.val+slow.val)\n",
    "            p = p.next\n",
    "            slow = slow.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        cur = head\n",
    "        reverse = None\n",
    "        ori = []\n",
    "        while cur:\n",
    "            ori.append(cur.val)\n",
    "            tmp = cur.next\n",
    "            cur.next = reverse\n",
    "            reverse = cur\n",
    "            cur = tmp\n",
    "        maxi = []\n",
    "        i = 0\n",
    "        while reverse:\n",
    "            maxi.append(reverse.val + ori[i])\n",
    "            reverse = reverse.next\n",
    "            i += 1\n",
    "        return max(maxi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        rets = []\n",
    "        h = ListNode()\n",
    "        while head:\n",
    "            t = head.next\n",
    "            head.next = h.next\n",
    "            h.next = head\n",
    "            rets.append(head.val)\n",
    "            head = t\n",
    "        head = h.next\n",
    "        for i in range(len(rets)):\n",
    "            rets[i] += head.val\n",
    "            head = head.next\n",
    "        return max(rets)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        if not head:\n",
    "            return 0\n",
    "        maxValue = float('-inf')\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        fast = head\n",
    "        slow = self.reverseList(slow)\n",
    "        while slow:\n",
    "            maxValue = max(fast.val + slow.val, maxValue)\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return maxValue\n",
    "    def reverseList(self, head:ListNode) -> ListNode:\n",
    "        pre, cur = None, head\n",
    "        while cur:\n",
    "            temp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = temp\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        slow, fast = head, head\n",
    "        max_val = 0\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        \n",
    "        prev, curr = None,slow\n",
    "        while curr:\n",
    "            #curr.next, prev, curr = prev, curr, curr.next\n",
    "            tmp = curr.next\n",
    "            curr.next = prev\n",
    "            prev = curr\n",
    "            curr = tmp\n",
    "\n",
    "        while prev:\n",
    "            max_val = max(max_val, head.val+prev.val)\n",
    "            prev = prev.next\n",
    "            head = head.next\n",
    "        return max_val\n",
    "\n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        res=0\n",
    "        slow,fast=head,head.next\n",
    "        while fast.next:\n",
    "            fast=fast.next.next\n",
    "            slow=slow.next\n",
    "        cur,dummy=slow.next,None\n",
    "        start=head\n",
    "        while cur:\n",
    "            t=cur.next\n",
    "            cur.next=dummy\n",
    "            dummy=cur\n",
    "            cur=t\n",
    "        while dummy:\n",
    "            res=max(res,dummy.val+start.val)\n",
    "            start=start.next\n",
    "            dummy=dummy.next\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        s = f = head\n",
    "        while f:\n",
    "            f = f.next.next\n",
    "            s = s.next\n",
    "        prev = None\n",
    "        while s:\n",
    "            nxt = s.next\n",
    "            s.next = prev\n",
    "            prev, s = s, nxt\n",
    "        maxSum = 0\n",
    "        while prev:\n",
    "            maxSum = max(maxSum, prev.val + head.val)\n",
    "            prev = prev.next\n",
    "            head = head.next\n",
    "        return maxSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        slow,fast = head,head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        pre = None\n",
    "        cur = slow\n",
    "        slow = head\n",
    "        while cur:\n",
    "            temp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = temp\n",
    "        result = 0\n",
    "        while pre and slow:\n",
    "            print(pre.val)\n",
    "            result = max(result,pre.val + slow.val)\n",
    "            pre = pre.next\n",
    "            slow = slow.next\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        if head.next.next == None:\n",
    "            # 节点数等于2\n",
    "            return head.val + head.next.val \n",
    "        \n",
    "        left_value = []\n",
    "        right_value = []\n",
    "        left = head\n",
    "        right = head.next\n",
    "        left_value.append(left.val)\n",
    "        right_value.append(right.val)\n",
    "\n",
    "        while right.next is not None and right.next.next is not None:\n",
    "            left.next = right.next\n",
    "            left = left.next \n",
    "            left_value.append(left.val)\n",
    "            right.next = left.next\n",
    "            right = right.next\n",
    "            right_value.append(right.val)\n",
    "        return max([x+y for x, y in zip(left_value, right_value[::-1])])\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        n = 0\n",
    "        def copy_head(head) -> Optional[ListNode]:\n",
    "            cur = head\n",
    "            or_head = None\n",
    "            pre = None\n",
    "            while cur is not None:\n",
    "                if or_head is None:\n",
    "                    or_head = ListNode(cur.val)\n",
    "                    pre = or_head\n",
    "                else:\n",
    "                    pre.next = ListNode(cur.val)\n",
    "                    pre = pre.next\n",
    "                cur = cur.next\n",
    "            return or_head\n",
    "\n",
    "        def reverse(re_head) -> Optional[ListNode]:\n",
    "            nonlocal n\n",
    "            if re_head is None:\n",
    "                n = 1\n",
    "                return re_head\n",
    "            elif re_head.next is None:\n",
    "                n = 2\n",
    "                return re_head\n",
    "            else:\n",
    "                pre = None\n",
    "                rear = re_head\n",
    "                cur = re_head\n",
    "                while cur is not None:\n",
    "                    rear = cur.next\n",
    "                    cur.next = pre\n",
    "                    pre = cur\n",
    "                    cur = rear\n",
    "                    re_head = pre\n",
    "                    n += 1\n",
    "            return re_head\n",
    "        or_head = copy_head(head)\n",
    "        re_head = reverse(head)\n",
    "        count = 0\n",
    "        ans = 0\n",
    "        cur_1 = or_head\n",
    "        cur_2 = re_head\n",
    "        while (count * 2) != n:\n",
    "            ans = max(ans, cur_1.val + cur_2.val)\n",
    "            cur_1 = cur_1.next\n",
    "            cur_2 = cur_2.next\n",
    "            count += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        res = []\n",
    "        n = 0\n",
    "        while head:\n",
    "            res.append(head.val)\n",
    "            head = head.next\n",
    "            n += 1\n",
    "        return max([res[i] + res[n-1-i] for i in range(n//2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        ans = []\n",
    "        while head:\n",
    "            ans.append(head.val)\n",
    "            head = head.next\n",
    "        n = len(ans)\n",
    "        return max(ans[i] + ans[n - i - 1] for i in range(n//2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        \"\"\"\n",
    "        cur=head\n",
    "        result=[]\n",
    "        maxNum=float(\"-inf\")\n",
    "        while cur:\n",
    "            result.append(cur.val)\n",
    "            cur=cur.next\n",
    "        n=len(result)\n",
    "        for i in range(n//2):\n",
    "            maxNum=max(maxNum,result[i]+result[n-1-i])\n",
    "        return maxNum\n",
    "        \"\"\"\n",
    "        slow=head\n",
    "        fast=head.next\n",
    "\n",
    "        while fast.next:\n",
    "            slow=slow.next\n",
    "            fast=fast.next.next\n",
    "        #反转链表\n",
    "        last=slow.next\n",
    "\n",
    "        while last.next:\n",
    "            cur=last.next\n",
    "            last.next=cur.next\n",
    "            cur.next=slow.next\n",
    "            slow.next=cur\n",
    "        ans=0\n",
    "        x,y=head,slow.next\n",
    "\n",
    "        while y:\n",
    "            ans=max(ans,x.val+y.val)\n",
    "            x,y=x.next,y.next\n",
    "        return ans\n",
    "\n",
    "        \n",
    "     \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        max_sum = 0\n",
    "        l = []\n",
    "        while head:\n",
    "            l.append(head.val)\n",
    "            head = head.next\n",
    "        n = len(l)\n",
    "        for i in range(int(len(l)/2)):\n",
    "            max_sum = max(max_sum, l[i]+l[n-i-1])\n",
    "        return max_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def pairSum(self, head: Optional[ListNode]) -> int:\n",
    "        a=[]\n",
    "        n=0\n",
    "        b=0\n",
    "        i=0\n",
    "        head1=head\n",
    "        while head1:\n",
    "            head1=head1.next\n",
    "            n+=1\n",
    "        while head:\n",
    "            if i<=n//2-1:\n",
    "                a.append(head.val)\n",
    "            else:\n",
    "                b=max(b,head.val+a.pop())\n",
    "            head=head.next\n",
    "            i+=1\n",
    "        return b\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
